package com.itheima.algorithm.dynamicprogramming;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <h3>Bellman-Ford 算法，求最短路径（可以处理负边）</h3>
 */
public class BellmanFord {

    static class Edge implements Comparable<Edge> {
        int from;
        int to;
        int weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

    /*
            f(v)用来表示从起点出发，到达v这个顶点的最短距离
            初始时
            f(v) = 0 当 v==起点 时
            f(v) = ∞ 当 v!=起点 时

            之后
            新           旧     所有from
            f(to) = min(f(to), f(from) + from.weight)

            找出递归公式，将当前问题分解成子问题，分阶段进行求解。
            求解过程中缓存子问题的解，避免重复计算。

            v1  v2  v3  v4  v5  V6
            0   ∞   ∞   ∞   ∞   ∞
            0   7   9   ∞   ∞   14  第一轮
                                    第二轮
                                    第三轮
                                    第四轮
                                    第五轮
     */
    public static void main(String[] args) {
        List<Edge> edges = Arrays.asList(
                new Edge(6, 5, 9),
                new Edge(4, 5, 6),
                new Edge(1, 6, 14),
                new Edge(3, 6, 2),
                new Edge(3, 4, 11),
                new Edge(2, 4, 15),
                new Edge(1, 3, 9),
                new Edge(1, 2, 7)
        );
        int[] dp = new int[7]; // 一维数组用来缓存结果
        dp[1] = 0;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        print(dp);
        for (int i = 0; i < dp.length - 2; i++) {
            for (Edge e : edges) {
                if (Integer.MAX_VALUE != dp[e.from]) {
                    dp[e.to] = Integer.min(dp[e.to], dp[e.from] + e.weight);
                }
            }
        }
        print(dp);
    }

    static void print(int[] dp) {
        System.out.println(Arrays.stream(dp)
                .mapToObj(i -> i == Integer.MAX_VALUE ? "∞" : String.valueOf(i))
                .collect(Collectors.joining(",", "[", "]")));
    }
}
